package leetcode.剑指offer.剑指II;

import leetcode.util.CommonUtils;
import leetcode.剑指offer.pojo.ListNode;
import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/8/7 17:16
 * @description：https://leetcode-cn.com/problems/LGjMqU/
 */
public class 剑指II_26_重排链表 {
    @Test
    public void test() {
        Solution solution = new Solution();
        ListNode head = new ListNode(1,
                new ListNode(2,
                        new ListNode(3,
                                new ListNode(4  ))));
        solution.reorderList(head);
        CommonUtils.list_listNode(head);
    }

    /*
    class Solution {
        public void reorderList(ListNode head) {
            HashMap<ListNode, ListNode> map = new HashMap<>();
            ListNode tmp = head;
            while (tmp.next != null) {
                map.put(tmp.next, tmp);
                tmp = tmp.next;
            }
            ListNode pre = head;
            ListNode end = tmp;
            while (pre != end && pre.next != end) {
                ListNode preNext = pre.next;
                ListNode endPre = map.get(end);
                pre.next = end;
                end.next = preNext;
                endPre.next = null;
                pre = preNext;
                end = endPre;
            }
        }
    }
     */

    //寻找链表中间点，反转后半部分链表，合并两个链表
    class Solution {
        public void reorderList(ListNode head) {
            if (head == null) return;
            ListNode middle_pre = findMiddle(head);
            ListNode middle = middle_pre.next;
            middle_pre.next = null;
            middle = reverseListNode(middle);
            merge(head, middle);
        }

        private void merge(ListNode A, ListNode B) {
            ListNode tmpA = A, tmpB = B;
            while (tmpA != null && tmpB != null) {
                ListNode tmpA_next = tmpA.next;
                ListNode tmpB_next = tmpB.next;

                tmpA.next = tmpB;
                tmpA = tmpA_next;

                tmpB.next = tmpA;
                tmpB = tmpB_next;
            }
        }

        private ListNode reverseListNode(ListNode middle) {
            if (middle == null) return null;
            ListNode curHead = new ListNode(-1);
            ListNode tmp = middle;
            ListNode next;
            while (tmp != null) {
                next = tmp.next;
                tmp.next = curHead.next;
                curHead.next = tmp;
                tmp = next;
            }
            return curHead.next;
        }

        private ListNode findMiddle(ListNode head) {
            if (head.next == null || head.next.next == null) return head;
            ListNode slow = head;
            ListNode fast = head;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return fast.next == null ? slow : slow.next;
        }
    }
}
